package solution;

import common.ListNode;

import java.util.HashSet;
import java.util.Set;
import java.util.Stack;

/**
 * @author zhangmin
 * @create 2021-08-06 10:19
 */
public class Solution_3List {
    /**===========================================================================================================================
     *删除链表中的节点
     * */
    public void deleteNode(ListNode node) {
        node.val=node.next.val;
        node.next=node.next.next;
    }


    /**===========================================================================================================================
     *反转链表
     * 1.栈，先进后出
     * 2.双链表
     * 3.迭代：在遍历链表时，将当前节点的next指针改为指向前一个节点。由于节点没有引用其前一个节点，因此必须事先存储其前一个节点。
     * 在更改引用之前，还需要存储后一个节点。最后返回新的头引用
     * 4.递归：
     * */
    public ListNode reverseList1(ListNode head) {
        if (head==null||head.next==null){
            return head;
        }
        Stack<ListNode> stack=new Stack<>();
        while (head!=null){
            stack.push(head);
            //System.out.println("stack="+head.val);
            head=head.next;
        }
        ListNode resnode=stack.pop();
        ListNode t=resnode;
        while (!stack.isEmpty()){
            ListNode tempnode=stack.pop();
            t.next=tempnode;
            t=t.next;
        }
        //最后一个结点就是反转前的头结点，一定要让他的next等于空，否则会构成环
        t.next=null;
        return resnode;
    }
    public ListNode reverseList2(ListNode head) {
        //新链表
        ListNode newHead=null;
        while (head!=null){
            ListNode next=head.next;
            //将当前节点作为新链表的头节点
            head.next=newHead;
            newHead= head;
            head=next;
        }
        return newHead;
    }
    public ListNode reverseList3(ListNode head) {
        //pre用来记录前序节点
        ListNode pre=null;
        ListNode nowNode=head;
        while (nowNode!=null){
            ListNode next=nowNode.next;
            nowNode.next=pre;
            pre=nowNode;
            nowNode=next;
        }
        return pre;
    }

    //递归：reverseList(ListNode head)表示输入一个节点 head，将「以 head 为起点」的链表反转，并返回反转之后的头结点。
    public ListNode reverseList(ListNode head) {
        if (head==null||head.next==null){
            return head;
        }
        ListNode newHead=reverseList(head.next);
        head.next.next=head;
        head.next=null;
        return newHead;
    }

    /**===========================================================================================================================
     *将链表的前 n 个节点反转（n <= 链表长度）
     * reverseN(ListNode head,int n)表示输入一个节点 head，将「以 head 为起点」的链表的前n个节点反转，并返回反转之后的头结点。
     * */
    ListNode successor = null; // 后驱节点
    ListNode reverseN(ListNode head, int n) {
        //base case 变为 n == 1，反转一个元素，就是它本身，同时要记录后驱节点。
        if(n==1){
            // 记录第 n + 1 个节点
            successor=head.next;
            return head;
        }
        ListNode newhead=reverseN(head.next,n-1);
        head.next.next=head;
        //刚才我们直接把 head.next 设置为 null，因为整个链表反转后原来的 head 变成了整个链表的最后一个节点。
        // 但现在 head 节点在递归反转之后不一定是最后一个节点了，所以要记录后驱 successor（第 n + 1 个节点），反转之后将 head 连接上。
        head.next=successor;
        return newhead;
    }

    /**===========================================================================================================================
     *92. 反转链表 II：
     * 给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。
     * */
    public ListNode reverseBetween1(ListNode head, int left, int right) {
        //如果 m == 1，就相当于反转链表开头的 n 个元素嘛，也就是我们刚才实现的功能：
        if (left==1){
            return reverseN(head,right);
        }
        //如果我们把 head 的索引视为 1，那么我们是想从第 m 个元素开始反转对吧；如果把 head.next 的索引视为 1 呢,
        // 那么相对于 head.next，反转的区间应该是从第 m - 1 个元素开始的；那么对于 head.next.next 呢
        head.next=reverseBetween1(head.next,left-1,right-1);
        return head;
    }

    public ListNode reverseBetween(ListNode head, int left, int right) {
        ListNode VNode=new ListNode(-1);
        VNode.next=head;
        ListNode pre=VNode;
        for (int i = 0; i < left-1; i++) {
            pre=pre.next;
        }

        ListNode leftNode=pre.next;
        ListNode rightNode=pre;
        for (int i = 0; i < right-left+1; i++) {
            rightNode=rightNode.next;
        }
        ListNode cut=rightNode.next;

        pre.next=null;
        rightNode.next=null;
        reverseList(leftNode);

        pre.next=rightNode;
        leftNode.next=cut;
        return VNode.next;
    }

    /**===========================================================================================================================
     *25. K 个一组翻转链表:
     * 给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。
     * */
    //递归：
    public ListNode reverseKGroup(ListNode head, int k) {
        if (head==null)
            return null;
        ListNode a,b;
        a=head;b=head;
        for (int i = 0; i < k; i++) {
            if (b==null)return head;
            b=b.next;
        }
        ListNode newHead=reverse(a,b);
        a.next=reverseKGroup(b,k);
        return newHead;
    }
    //反转[a,b)内的元素
    ListNode reverse(ListNode a, ListNode b) {
        ListNode pre,cur,next;
        pre=null;cur=a;next=null;
        while (cur!=b){
            next=cur.next;
            cur.next=pre;
            pre=cur;
            cur=next;
        }
        return pre;
    }

    /**===========================================================================================================================
     *合并两个有序链表
     * */
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        }
        if (l2==null){
            return l1;
        }
        ListNode resHead=null;
        if (l1.val<l2.val){
            resHead=l1;
            l1=l1.next;
        }else {
            resHead=l2;
            l2=l2.next;
        }
        ListNode resnode=resHead;
        while (l1!=null&&l2!=null){
            if (l1.val<l2.val){
                resnode.next=l1;
                l1=l1.next;
            }else {
                resnode.next=l2;
                l2=l2.next;
            }
            resnode=resnode.next;
        }

        resnode.next=l1!=null?l1:l2;
        return resHead;

    }




    /**===========================================================================================================================
     *回文链表
     * 1.双指针：将链表的值复制到数组中后再判断-----时间O(n)，空间复杂度：O(n)
     * 快慢指针：将后半部分反转后比较--空间复杂度：O(1)
     * 2.栈
     * 3.递归
     * */
    public boolean isPalindrome1(ListNode head) {
        Stack<Integer> stack=new Stack<>();
        ListNode t=head;
        while (t!=null){
            stack.push(t.val);
            t=t.next;
        }
        if (stack.isEmpty()){
            return true;
        }
        while (head!=null){
            if (head.val!=stack.pop()){
                return false;
            }
            head=head.next;
        }
        return true;
    }
    public boolean isPalindrome2(ListNode head) {
        if (head==null){
            return true;
        }
        int len=0;
        ListNode t=head;
        //求出head的长度
        while (t!=null){
            len++;
            t=t.next;
        }
        //定位到中间节点
        ListNode helfHead=head;
        for (int i = 0; i < len/2; i++) {
            helfHead=helfHead.next;
        }
        ListNode revsHead=reverseList(helfHead);
        ListNode p1=head;
        ListNode p2=revsHead;
        boolean res=true;
        while (res&&p2!=null){
            if (p1.val!=p2.val){
                res=false;
            }
            p1=p1.next;
            p2=p2.next;
        }
        return res;
    }

    //3.递归：实际上就是把链表节点放入一个栈，然后再拿出来，这时候元素顺序就是反的，只不过我们利用的是递归函数的堆栈而已。
    // 左侧指针
    ListNode left;
    public boolean isPalindrome3(ListNode head) {
        left=head;
        return traverse(head);
    }
    boolean traverse(ListNode right) {
        if (right==null)return true;
        boolean res=traverse(right.next);
        //后续遍历的代码
        res=res&&(right.val==left.val);
        left=left.next;
        return res;
    }
    /*1.2快慢指针
    先通过「双指针技巧」中的快慢指针来找到链表的中点
    如果fast指针没有指向null，说明链表长度为奇数，slow还要再前进一步，从slow开始反转后面的链表，现在就可以开始比较回文串了：
    */
    public boolean isPalindrome4(ListNode head) {
        ListNode slow, fast;
        slow=fast=head;
        //pq用来恢复原链表的结构
        ListNode p=slow,q=null;
        while (fast!=null&&fast.next!=null){
            p=slow;
            slow=slow.next;
            fast=fast.next.next;
        }
        // slow 指针现在指向链表中点
        //fast不为空则链表为奇数个，需要在向后一个
        if (fast!=null){
            p=slow;
            slow=slow.next;
        }
        //从slow开始反转后面的链表
        ListNode left=head;
        ListNode right=reverseList(slow);
        q=right;
        while (right!=null){
            if (left.val!=right.val)return false;
            left=left.next;
            right=right.next;
        }
        //恢复链表的原始结构
        p.next=reverseList(q);
        return true;
    }





    /**===========================================================================================================================
     * 快慢指针 141. 环形链表
     * 1.放到集合set中
     * 2.快慢指针解决:慢指针针每次走一步，快指针每次走两步，如果相遇就说明有环，如果有一个为空说明没有环
     * */
    public boolean hasCycle1(ListNode head) {
        Set<ListNode> set=new HashSet<>();
        while (head!=null){
            if (set.contains(head)){
                return true;
            }
            set.add(head);
            head=head.next;
        }
        return false;
    }
    public boolean hasCycle(ListNode head) {
        if (head==null){
            return false;
        }
        if (head.next==null){
            return false;
        }
        ListNode slow=head;
        ListNode fast=head.next;
        while (fast!=null&&fast.next!=null){
            slow=slow.next;
            fast=fast.next.next;
            if (slow==fast){
                return true;
            }
        }
        return false;
    }


    /**===========================================================================================================================
     * 快慢指针 142. 环形链表 II
     * 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
     * 当快慢指针相遇时，让其中任一个指针指向头节点，然后让它俩以相同速度前进，再次相遇时所在的节点位置就是环开始的位置。
     * */
    public ListNode detectCycle(ListNode head) {
        ListNode slow=head;
        ListNode fast=head;
        while (fast!=null&&fast.next!=null){
            slow=slow.next;
            fast=fast.next.next;
            if (slow==fast){
                break;
            }
        }

        if (fast==null||fast.next==null){
            return null;
        }
        slow=head;
        while (slow!=fast){
            fast=fast.next;
            slow=slow.next;
        }
        return slow;
    }


    /**===========================================================================================================================
     * 快慢指针 876. 链表的中间结点
     * 给定一个头结点为 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。
     * 可以让快指针一次前进两步，慢指针一次前进一步，当快指针到达链表尽头时，慢指针就处于链表的中间位置。
     * */
    public ListNode middleNode(ListNode head) {
        ListNode slow=head;
        ListNode fast=head;
        while (fast!=null&&fast.next!=null){
            slow=slow.next;
            fast=fast.next.next;
        }
        return slow;
    }

    /**===========================================================================================================================
     * 快慢指针 19. 删除链表的倒数第 N 个结点
     * 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
     * 让快指针先走 n 步，然后快慢指针开始同速前进。这样当快指针走到链表末尾 null 时，慢指针所在的位置就是倒数第 n 个链表节点（n 不会超过链表长度）。
     * */
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode slow=head;
        ListNode fast=head;
        //快指针先出发n步
        while (n-->0){
            fast=fast.next;
        }
        if (fast==null){
            // 如果此时快指针走到头了，
            // 说明倒数第 n 个节点就是第一个节点
            return head.next;
        }
        //快慢指针同时前进，知道快指针到大最后，慢指针的下一个位置就时需要删除的倒数第n个节点
        while (fast!=null&&fast.next!=null){
            fast=fast.next;
            slow=slow.next;
        }
        // slow.next 就是倒数第 n 个节点，删除它
        slow.next=slow.next.next;
        return head;
    }
    //常规解法，求出链表长度，然后定位到倒数第n个
    public ListNode removeNthFromEnd1(ListNode head, int n) {
        int len=0;
        ListNode t=head;
        //求出head的长度
        while (t!=null){
            len++;
            t=t.next;
        }
        int index=len-n;
        //若删除的是头节点
        if (index==0){
            return head.next;
        }
        t=head;
        //定位到需要删除的前一个节点
        for (int i = 0; i < index-1; i++) {
            t=t.next;
        }
        t.next=t.next.next;
        return head;
    }

    /**===========================================================================================================================
     *  160. 相交链表
     *  给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
     * */
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA==null||headB==null) return null;
        ListNode pa=headA,pb=headB;
        while(pa!=pb){
            if(pa==null){
                pa=headB;
            }else if(pb==null){
                pb=headA;
            }else{
                pa=pa.next;
                pb=pb.next;
            }
        }
        return pa;
    }

    /**===========================================================================================================================
     *快慢指针 83. 删除排序链表中的重复元素
     * 存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除所有重复的元素，使每个元素 只出现一次 。返回同样按升序排列的结果链表。
     * */
    public ListNode deleteDuplicates(ListNode head) {
        if (head==null) return null;
        ListNode slow=head,fast=head;
        while (fast!=null){
            if (fast.val!=slow.val){
                slow.next=fast;
                slow=slow.next;
            }
            fast=fast.next;
        }
        slow.next= null;
        return head;

    }


    public static void main(String[] args) {
        ListNode head1=new ListNode(1);
        ListNode head2=new ListNode(1,new ListNode(2,new ListNode(2,new ListNode(1))));
        Solution_3List object=new Solution_3List();
//        ListNode res=object.removeNthFromEnd(head,2);
//        ListNode res=object.reverseList(head1);
//        ListNode res=object.mergeTwoLists(head1,head2);
//        System.out.println(object.isPalindrome(head2));;
        System.out.println(object.hasCycle(head1));
/*        while (res!=null){
            System.out.println(res.val);
            res=res.next;
        }*/


    }
}
